/*
@Copyright:LintCode
@Author:   tjyemail
@Problem:  http://www.lintcode.com/problem/subtree
@Language: C++
@Datetime: 16-02-09 05:19
*/

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
    bool isEqual(TreeNode *T1,TreeNode *T2){
        if (T1==T2 && T1==NULL)
            return true;
        if (T1==NULL || T2==NULL)
            return false;
        if (T1->val != T2->val)
            return false;
        bool flag = isEqual(T1->left,T2->left);
        if (!flag)
            return false;
        return isEqual(T1->right,T2->right);
    }
public:
    /**
     * @param T1, T2: The roots of binary tree.
     * @return: True if T2 is a subtree of T1, or false.
     */
    bool isSubtree(TreeNode *T1, TreeNode *T2) {
        // write your code here
        if (T2==NULL)
            return true;
        if (T1==NULL)
            return false;
        bool flag;
        if (T1->val == T2->val){
            flag = isEqual(T1,T2);
            if (flag)
                return true;
        }
        flag = isSubtree(T1->left,T2);
        if (flag)
            return true;
        flag = isSubtree(T1->right,T2);
        return flag;
    }
};